<!DOCTYPE html>
<html lang="en-US">
  <head>
    <meta charset="utf-8">
    <meta name="viewport" content="width=device-width,initial-scale=1">
    <title>算法 | fengrixin</title>
    <meta name="generator" content="VuePress 1.8.2">
    <link rel="icon" href="/favicon.ico">
    <script>
         (function(){
            var html = document.createElement('script');
            html.src = 'https://www.googletagmanager.com/gtag/js?id=UA-166891571-1';
            var script = document.getElementsByTagName('script')[0]'
            script.parentNode.insertBefore(html, script);
            
            window.dataLayer = window.dataLayer || [];
            function gtag(){dataLayer.push(arguments)}
            gtag('js', new Date());
            gtag('config', 'UA-166891571-1');
         })();
        </script>
    <meta name="description" content="I don't know anything with certainty, but seeing the stars makes me dream.">
    <meta name="keywords" content="冯日新, fengrixin, rixin, 飘渺云轩">
    <meta name="author" content="rixin, s2675563468, fengrixin@yeah.net">
    <meta name="copyright" content="rixin">
    <meta name="renderer" content="webkit">
    
    <link rel="preload" href="/assets/css/0.styles.52cdc27a.css" as="style"><link rel="preload" href="/assets/js/app.0696c23a.js" as="script"><link rel="preload" href="/assets/js/2.96f039f8.js" as="script"><link rel="preload" href="/assets/js/10.473b7d15.js" as="script"><link rel="prefetch" href="/assets/js/11.0c193dec.js"><link rel="prefetch" href="/assets/js/12.c4d9d484.js"><link rel="prefetch" href="/assets/js/13.dce50cfa.js"><link rel="prefetch" href="/assets/js/14.eecb5cc3.js"><link rel="prefetch" href="/assets/js/15.e0473034.js"><link rel="prefetch" href="/assets/js/16.25b14741.js"><link rel="prefetch" href="/assets/js/17.c016c8f3.js"><link rel="prefetch" href="/assets/js/18.71195568.js"><link rel="prefetch" href="/assets/js/19.1dfd44c0.js"><link rel="prefetch" href="/assets/js/20.abde37ca.js"><link rel="prefetch" href="/assets/js/21.af59917b.js"><link rel="prefetch" href="/assets/js/22.d2f7b52b.js"><link rel="prefetch" href="/assets/js/23.ec5c07a5.js"><link rel="prefetch" href="/assets/js/24.eae97f7d.js"><link rel="prefetch" href="/assets/js/25.2f09818a.js"><link rel="prefetch" href="/assets/js/26.7ae2d77c.js"><link rel="prefetch" href="/assets/js/27.a3963c70.js"><link rel="prefetch" href="/assets/js/28.eadcc4e5.js"><link rel="prefetch" href="/assets/js/29.61cf8d1d.js"><link rel="prefetch" href="/assets/js/3.dd8204a7.js"><link rel="prefetch" href="/assets/js/30.7db889fa.js"><link rel="prefetch" href="/assets/js/31.fb075f3c.js"><link rel="prefetch" href="/assets/js/4.cf123337.js"><link rel="prefetch" href="/assets/js/5.abe0fc83.js"><link rel="prefetch" href="/assets/js/6.d9ded6eb.js"><link rel="prefetch" href="/assets/js/7.a054e416.js"><link rel="prefetch" href="/assets/js/8.f0b3a07f.js"><link rel="prefetch" href="/assets/js/9.f6495dca.js">
    <link rel="stylesheet" href="/assets/css/0.styles.52cdc27a.css">
  </head>
  <body>
    <div id="app" data-server-rendered="true"><div class="theme-container"><header class="navbar"><div class="sidebar-button"><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" role="img" viewBox="0 0 448 512" class="icon"><path fill="currentColor" d="M436 124H12c-6.627 0-12-5.373-12-12V80c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12zm0 160H12c-6.627 0-12-5.373-12-12v-32c0-6.627 5.373-12 12-12h424c6.627 0 12 5.373 12 12v32c0 6.627-5.373 12-12 12z"></path></svg></div> <a href="/" class="home-link router-link-active"><!----> <span class="site-name">fengrixin</span></a> <div class="links"><div class="search-box"><input aria-label="Search" autocomplete="off" spellcheck="false" value=""> <!----></div> <nav class="nav-links can-hide"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="地基" class="dropdown-title"><span class="title">地基</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/learn/algorithm/" class="nav-link router-link-active">数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/learn/browser/" class="nav-link">浏览器工作原理</a></li><li class="dropdown-item"><!----> <a href="/learn/js/es6.html" class="nav-link">JavaScript</a></li><li class="dropdown-item"><!----> <a href="/learn/css/" class="nav-link">CSS</a></li><li class="dropdown-item"><!----> <a href="/learn/html/" class="nav-link">HTML</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="楼层" class="dropdown-title"><span class="title">楼层</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/learn/vue/" class="nav-link">Vue</a></li><li class="dropdown-item"><!----> <a href="/learn/node/" class="nav-link">Node.js</a></li><li class="dropdown-item"><!----> <a href="/learn/mini/index.html" class="nav-link">小程序</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="电梯" class="dropdown-title"><span class="title">电梯</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/learn/tools/chain.html" class="nav-link">工具链</a></li><li class="dropdown-item"><!----> <a href="/learn/tools/publish.html" class="nav-link">发布系统</a></li><li class="dropdown-item"><!----> <a href="/learn/tools/monitor.html" class="nav-link">监控系统</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="看一看" class="dropdown-title"><span class="title">看一看</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>仓库</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/watch/repository.html" class="nav-link">第三方库</a></li><li class="dropdown-subitem"><a href="/watch/website.html" class="nav-link">好玩的网站</a></li><li class="dropdown-subitem"><a href="/watch/article.html" class="nav-link">牛掰的文章</a></li><li class="dropdown-subitem"><a href="/watch/plugin.html" class="nav-link">扩展&amp;插件</a></li></ul></li><li class="dropdown-item"><h4>作品</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="http://www.5you.com/apk/384161.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  微冷知识
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></li></ul></div></div><div class="nav-item"><a href="https://github.com/fengrixin" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav></div></header> <div class="sidebar-mask"></div> <aside class="sidebar"><nav class="nav-links"><div class="nav-item"><a href="/" class="nav-link">首页</a></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="地基" class="dropdown-title"><span class="title">地基</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/learn/algorithm/" class="nav-link router-link-active">数据结构和算法</a></li><li class="dropdown-item"><!----> <a href="/learn/browser/" class="nav-link">浏览器工作原理</a></li><li class="dropdown-item"><!----> <a href="/learn/js/es6.html" class="nav-link">JavaScript</a></li><li class="dropdown-item"><!----> <a href="/learn/css/" class="nav-link">CSS</a></li><li class="dropdown-item"><!----> <a href="/learn/html/" class="nav-link">HTML</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="楼层" class="dropdown-title"><span class="title">楼层</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/learn/vue/" class="nav-link">Vue</a></li><li class="dropdown-item"><!----> <a href="/learn/node/" class="nav-link">Node.js</a></li><li class="dropdown-item"><!----> <a href="/learn/mini/index.html" class="nav-link">小程序</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="电梯" class="dropdown-title"><span class="title">电梯</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><!----> <a href="/learn/tools/chain.html" class="nav-link">工具链</a></li><li class="dropdown-item"><!----> <a href="/learn/tools/publish.html" class="nav-link">发布系统</a></li><li class="dropdown-item"><!----> <a href="/learn/tools/monitor.html" class="nav-link">监控系统</a></li></ul></div></div><div class="nav-item"><div class="dropdown-wrapper"><button type="button" aria-label="看一看" class="dropdown-title"><span class="title">看一看</span> <span class="arrow right"></span></button> <ul class="nav-dropdown" style="display:none;"><li class="dropdown-item"><h4>仓库</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="/watch/repository.html" class="nav-link">第三方库</a></li><li class="dropdown-subitem"><a href="/watch/website.html" class="nav-link">好玩的网站</a></li><li class="dropdown-subitem"><a href="/watch/article.html" class="nav-link">牛掰的文章</a></li><li class="dropdown-subitem"><a href="/watch/plugin.html" class="nav-link">扩展&amp;插件</a></li></ul></li><li class="dropdown-item"><h4>作品</h4> <ul class="dropdown-subitem-wrapper"><li class="dropdown-subitem"><a href="http://www.5you.com/apk/384161.html" target="_blank" rel="noopener noreferrer" class="nav-link external">
  微冷知识
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></li></ul></div></div><div class="nav-item"><a href="https://github.com/fengrixin" target="_blank" rel="noopener noreferrer" class="nav-link external">
  GitHub
  <span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></div> <!----></nav>  <ul class="sidebar-links"><li><a href="/learn/algorithm/" aria-current="page" class="sidebar-link">数据结构和算法</a></li><li><a href="/learn/algorithm/data_structure.html" class="sidebar-link">数据结构</a></li><li><a href="/learn/algorithm/algorithm.html" aria-current="page" class="active sidebar-link">算法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#闲暇时间刷刷算法-提高下逻辑思维" class="sidebar-link">闲暇时间刷刷算法，提高下逻辑思维</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#排序算法" class="sidebar-link">排序算法</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#冒泡排序" class="sidebar-link">冒泡排序</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#快速排序" class="sidebar-link">快速排序</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#堆排序" class="sidebar-link">堆排序</a></li></ul></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#二分查找" class="sidebar-link">二分查找</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#哈希算法" class="sidebar-link">哈希算法</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#深度和广度优先搜索" class="sidebar-link">深度和广度优先搜索</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#贪心算法" class="sidebar-link">贪心算法</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#分治算法" class="sidebar-link">分治算法</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#回溯算法" class="sidebar-link">回溯算法</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#动态规划" class="sidebar-link">动态规划</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#算法题" class="sidebar-link">算法题</a><ul class="sidebar-sub-headers"><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#数组" class="sidebar-link">数组</a></li><li class="sidebar-sub-header"><a href="/learn/algorithm/algorithm.html#字符串" class="sidebar-link">字符串</a></li></ul></li></ul></li></ul> </aside> <main class="page"> <div class="theme-default-content content__default"><blockquote><p>算法的本质是寻找规律并实现</p> <p>如果寻找规律？找出输入和输出的关系，寻找突破口</p> <p>如何实现？实现是程序+数据结构的结合体</p></blockquote> <h2 id="闲暇时间刷刷算法-提高下逻辑思维"><a href="#闲暇时间刷刷算法-提高下逻辑思维" class="header-anchor">#</a> 闲暇时间刷刷算法，提高下逻辑思维</h2> <p><a href="https://leetcode-cn.com/u/rixin" target="_blank" rel="noopener noreferrer">力扣主页<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p> <h2 id="排序算法"><a href="#排序算法" class="header-anchor">#</a> 排序算法</h2> <p>按时间复杂度区分的话：</p> <ul><li>O(n^2)：冒泡排序、选择排序、插入排序</li> <li>O(nlogn)：快速排序、归并排序、堆排序</li> <li>O(n)：计数排序、桶排序、基数排序</li></ul> <p>排序还可以根据其稳定性划分为「稳定排序」和「不稳定排序」。何为不稳定性呢？就是值相同的元素在排序后改变了原来的位置。</p> <ul><li>稳 定：冒泡排序、插入排序、归并排序、计数排序、桶排序、基数排序</li> <li>不稳定：选择排序、快速排序、堆排序</li></ul> <h3 id="冒泡排序"><a href="#冒泡排序" class="header-anchor">#</a> 冒泡排序</h3> <p>冒泡排序非常简单，就是遍历一组数据（数据长度-1次），相邻两个数字进行对比，然后交换位置</p> <p>冒泡排序是一种稳定排序。</p> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token keyword">function</span> <span class="token function">sort</span><span class="token punctuation">(</span><span class="token parameter">arr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> leni <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> leni<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> lenj <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> lenj<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&gt;</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">return</span> arr<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token function">sort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
</code></pre></div><p>优化：</p> <ul><li>使用一个变量进行标记，如果在某轮排序中，没有元素交换，则说明数列已然有序，可以直接跳出循环，节省循环次数</li></ul> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token keyword">function</span> <span class="token function">sort</span><span class="token punctuation">(</span><span class="token parameter">arr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> leni <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> leni<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> isSorted <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> lenj <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> i <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> lenj<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&gt;</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
        isSorted <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token comment">// 本轮有交换</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>isSorted<span class="token punctuation">)</span> <span class="token keyword">break</span>  <span class="token comment">// 本轮无交换，跳出循环</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">return</span> arr<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token function">sort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
</code></pre></div><ul><li>记录下最后一次元素交换的位置，该位置即为无序数列的边界，往后就是有序区了，无需再遍历下去</li></ul> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token keyword">function</span> <span class="token function">sort</span><span class="token punctuation">(</span><span class="token parameter">arr</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> leni <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span> i <span class="token operator">&lt;</span> leni<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> isSorted <span class="token operator">=</span> <span class="token boolean">true</span><span class="token punctuation">;</span>
    <span class="token keyword">let</span> sortBorder <span class="token operator">=</span> arr<span class="token punctuation">.</span>length <span class="token operator">-</span> <span class="token number">1</span><span class="token punctuation">;</span>
    <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span> j <span class="token operator">&lt;</span> sortBorder<span class="token punctuation">;</span> j<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">let</span> temp <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">;</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span>arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">&gt;</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        temp <span class="token operator">=</span> arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>j<span class="token punctuation">]</span> <span class="token operator">=</span> arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span><span class="token punctuation">;</span>
        arr<span class="token punctuation">[</span>j <span class="token operator">+</span> <span class="token number">1</span><span class="token punctuation">]</span> <span class="token operator">=</span> temp<span class="token punctuation">;</span>
        isSorted <span class="token operator">=</span> <span class="token boolean">false</span><span class="token punctuation">;</span> <span class="token comment">// 本轮有交换</span>
        sortBorder <span class="token operator">=</span> j<span class="token punctuation">;</span> <span class="token comment">// 记录最后一次交换的位置</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
    <span class="token keyword">if</span> <span class="token punctuation">(</span>isSorted<span class="token punctuation">)</span> <span class="token keyword">break</span>  <span class="token comment">// 本轮无交换，跳出循环</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">return</span> arr<span class="token punctuation">;</span>
<span class="token punctuation">}</span>

<span class="token function">sort</span><span class="token punctuation">(</span><span class="token punctuation">[</span><span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">)</span>
</code></pre></div><ul><li>鸡尾酒排序：像钟摆一样左右交替循环进行排序，适用于大部分元素已经有序的情况</li></ul> <h3 id="快速排序"><a href="#快速排序" class="header-anchor">#</a> 快速排序</h3> <p>同冒泡一样也属于交换排序，不同于冒泡每次只把一个元素冒泡到数列一端</p> <p>快速排序则是 <strong>「在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列一边，比它小的元素移动到数列的另一边，从而把数列拆解成两个部分」</strong></p> <p>这种思路叫做「分治法」</p> <h3 id="堆排序"><a href="#堆排序" class="header-anchor">#</a> 堆排序</h3> <h2 id="二分查找"><a href="#二分查找" class="header-anchor">#</a> 二分查找</h2> <h2 id="哈希算法"><a href="#哈希算法" class="header-anchor">#</a> 哈希算法</h2> <h2 id="深度和广度优先搜索"><a href="#深度和广度优先搜索" class="header-anchor">#</a> 深度和广度优先搜索</h2> <h2 id="贪心算法"><a href="#贪心算法" class="header-anchor">#</a> 贪心算法</h2> <h2 id="分治算法"><a href="#分治算法" class="header-anchor">#</a> 分治算法</h2> <h2 id="回溯算法"><a href="#回溯算法" class="header-anchor">#</a> 回溯算法</h2> <h2 id="动态规划"><a href="#动态规划" class="header-anchor">#</a> 动态规划</h2> <h2 id="算法题"><a href="#算法题" class="header-anchor">#</a> 算法题</h2> <h3 id="数组"><a href="#数组" class="header-anchor">#</a> 数组</h3> <ul><li><p><a href="https://leetcode-cn.com/problems/two-sum" target="_blank" rel="noopener noreferrer">两数之和<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p></li> <li><p><a href="https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array" target="_blank" rel="noopener noreferrer">删除排序数组中的重复项<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p></li> <li><p><a href="https://leetcode-cn.com/problems/merge-sorted-array" target="_blank" rel="noopener noreferrer">合并两个有序数组<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></p></li> <li><p>已知如下数组，编写一个程序将数组扁平化去并除其中重复部分数据，最终得到一个升序且不重复的数组</p></li></ul> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token keyword">const</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token punctuation">[</span><span class="token number">1</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">,</span> <span class="token number">2</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">3</span><span class="token punctuation">,</span> <span class="token number">4</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">,</span> <span class="token number">5</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">6</span><span class="token punctuation">,</span> <span class="token number">7</span><span class="token punctuation">,</span> <span class="token number">8</span><span class="token punctuation">,</span> <span class="token number">9</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">11</span><span class="token punctuation">,</span> <span class="token number">12</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">12</span><span class="token punctuation">,</span> <span class="token number">13</span><span class="token punctuation">,</span> <span class="token punctuation">[</span><span class="token number">14</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">]</span><span class="token punctuation">,</span> <span class="token number">10</span><span class="token punctuation">]</span>

console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>Array<span class="token punctuation">.</span><span class="token function">from</span><span class="token punctuation">(</span><span class="token keyword">new</span> <span class="token class-name">Set</span><span class="token punctuation">(</span>arr<span class="token punctuation">.</span><span class="token function">flat</span><span class="token punctuation">(</span><span class="token number">Infinity</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">)</span><span class="token punctuation">.</span><span class="token function">sort</span><span class="token punctuation">(</span><span class="token punctuation">(</span><span class="token parameter">a<span class="token punctuation">,</span> b</span><span class="token punctuation">)</span> <span class="token operator">=&gt;</span> a <span class="token operator">-</span> b<span class="token punctuation">)</span><span class="token punctuation">)</span>
</code></pre></div><ul><li>请把两个数组 ['A1', 'A2', 'B1', 'B2', 'C1', 'C2', 'D1', 'D2'] 和 ['A', 'B', 'C', 'D']
，合并为 ['A1', 'A2', 'A', 'B1', 'B2', 'B', 'C1', 'C2', 'C', 'D1', 'D2', 'D']。</li></ul> <div class="language-javascript extra-class"><pre class="language-javascript"><code><span class="token keyword">function</span> <span class="token function">concatArr</span><span class="token punctuation">(</span><span class="token parameter">arr1<span class="token punctuation">,</span> arr2</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
  <span class="token keyword">let</span> arr <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token operator">...</span>arr1<span class="token punctuation">]</span>
  <span class="token keyword">let</span> currentIndex <span class="token operator">=</span> <span class="token number">0</span>
  <span class="token keyword">for</span> <span class="token punctuation">(</span><span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span><span class="token punctuation">,</span> len <span class="token operator">=</span> arr2<span class="token punctuation">.</span>length<span class="token punctuation">;</span> i <span class="token operator">&lt;</span> len<span class="token punctuation">;</span> i<span class="token operator">++</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
    <span class="token keyword">let</span> re <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">RegExp</span><span class="token punctuation">(</span>arr2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
    <span class="token keyword">while</span> <span class="token punctuation">(</span>currentIndex <span class="token operator">&lt;</span> arr<span class="token punctuation">.</span>length<span class="token punctuation">)</span> <span class="token punctuation">{</span>
      <span class="token keyword">if</span> <span class="token punctuation">(</span><span class="token operator">!</span>re<span class="token punctuation">.</span><span class="token function">test</span><span class="token punctuation">(</span>arr<span class="token punctuation">[</span><span class="token operator">++</span>currentIndex<span class="token punctuation">]</span><span class="token punctuation">)</span><span class="token punctuation">)</span> <span class="token punctuation">{</span>
        arr<span class="token punctuation">.</span><span class="token function">splice</span><span class="token punctuation">(</span>currentIndex<span class="token punctuation">,</span> <span class="token number">0</span><span class="token punctuation">,</span> arr2<span class="token punctuation">[</span>i<span class="token punctuation">]</span><span class="token punctuation">)</span>
        <span class="token keyword">break</span>
      <span class="token punctuation">}</span>
    <span class="token punctuation">}</span>
  <span class="token punctuation">}</span>
  <span class="token keyword">return</span> arr
<span class="token punctuation">}</span>

<span class="token keyword">let</span> arr1 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token string">'A1'</span><span class="token punctuation">,</span> <span class="token string">'A2'</span><span class="token punctuation">,</span> <span class="token string">'B1'</span><span class="token punctuation">,</span> <span class="token string">'B2'</span><span class="token punctuation">,</span> <span class="token string">'C1'</span><span class="token punctuation">,</span> <span class="token string">'C2'</span><span class="token punctuation">,</span> <span class="token string">'D1'</span><span class="token punctuation">,</span> <span class="token string">'D2'</span><span class="token punctuation">]</span>
<span class="token keyword">let</span> arr2 <span class="token operator">=</span> <span class="token punctuation">[</span><span class="token string">'A'</span><span class="token punctuation">,</span> <span class="token string">'B'</span><span class="token punctuation">,</span> <span class="token string">'C'</span><span class="token punctuation">,</span> <span class="token string">'D'</span><span class="token punctuation">]</span>
console<span class="token punctuation">.</span><span class="token function">log</span><span class="token punctuation">(</span>arr1<span class="token punctuation">,</span> arr2<span class="token punctuation">,</span> <span class="token function">concatArr</span><span class="token punctuation">(</span>arr1<span class="token punctuation">,</span> arr2<span class="token punctuation">)</span><span class="token punctuation">)</span>
</code></pre></div><h3 id="字符串"><a href="#字符串" class="header-anchor">#</a> 字符串</h3> <ul><li><a href="https://leetcode-cn.com/problems/reverse-string" target="_blank" rel="noopener noreferrer">反转字符串<span><svg xmlns="http://www.w3.org/2000/svg" aria-hidden="true" focusable="false" x="0px" y="0px" viewBox="0 0 100 100" width="15" height="15" class="icon outbound"><path fill="currentColor" d="M18.8,85.1h56l0,0c2.2,0,4-1.8,4-4v-32h-8v28h-48v-48h28v-8h-32l0,0c-2.2,0-4,1.8-4,4v56C14.8,83.3,16.6,85.1,18.8,85.1z"></path> <polygon fill="currentColor" points="45.7,48.7 51.3,54.3 77.2,28.5 77.2,37.2 85.2,37.2 85.2,14.9 62.8,14.9 62.8,22.9 71.5,22.9"></polygon></svg> <span class="sr-only">(opens new window)</span></span></a></li></ul></div> <footer class="page-edit"><!----> <div class="last-updated"><span class="prefix">上次更新:</span> <span class="time">9/16/2021, 3:28:52 PM</span></div></footer> <div class="page-nav"><p class="inner"><span class="prev">
      ←
      <a href="/learn/algorithm/data_structure.html" class="prev">数据结构</a></span> <!----></p></div> </main></div><div class="global-ui"></div></div>
    <script src="/assets/js/app.0696c23a.js" defer></script><script src="/assets/js/2.96f039f8.js" defer></script><script src="/assets/js/10.473b7d15.js" defer></script>
  </body>
</html>
